package week02

// 329. 矩阵中的最长递增路径
// https://leetcode-cn.com/problems/longest-increasing-path-in-a-matrix/

func longestIncreasingPath(matrix [][]int) int {
	var ans = 0
	// 记忆每个点出发能走的最长路径
	var maxLen [][]int
	for x := range matrix {
		sli := make([]int, len(matrix[x]))
		for y := range sli {
			sli[y] = -1
		}
		maxLen = append(maxLen, sli)
	}

	for x := range matrix {
		for y := range matrix[x] {
			ans = max(ans, dfs(matrix, maxLen, x, y))
		}
	}
	return ans
}

func dfs(matrix [][]int, maxLen [][]int, x, y int) int {
	if maxLen[x][y] != -1 {
		return maxLen[x][y]
	}
	maxLen[x][y] = 1
	for dir := range dx {
		nx := x + dx[dir]
		ny := y + dy[dir]

		if !isValid(matrix, nx, ny) {
			continue
		}
		if matrix[nx][ny] > matrix[x][y] {
			maxLen[x][y] = max(maxLen[x][y], dfs(matrix, maxLen, nx, ny)+1)
		}
	}
	return maxLen[x][y]
}

func isValid(matrix [][]int, x, y int) bool {
	return x >= 0 && y >= 0 && x < len(matrix) && y < len(matrix[x])
}

func max(x, y int) int {
	if x > y {
		return x
	}
	return y
}

var dx = [4]int{0, 1, 0, -1}
var dy = [4]int{1, 0, -1, 0}